Okay, good morning. Welcome to the third lecture of this quantum computing course. So two things

before I start, I actually just wanted to update the lecture notes so that they would include the

material of this lecture, but somehow something didn't really work. So I'll try to do this right

after. The second thing I wanted to say is, so I didn't anticipate that many of you here,

which I'm very happy you are, right? But for that reason, we only have one exercise tutorial group

and I've tried to get a second tutor to run a second group, but I haven't been successful so far.

So I can promise we will be able to offer a second group after Christmas because then a

new group member in my group is coming. I'm not sure I will be able to do something about it before

Christmas. I keep trying. I'm sorry about the situation, but I couldn't fix it since last week.

Okay, so having said that, let me start with the lecture of today. Before going to the new material,

a few things about what we were talking about in the last lecture as a reminder.

So last lecture was about composite quantum systems

where a general state of such a composite quantum system can be written

as a sum over the degrees of freedom of one of the subsystems times a sum over the degrees

of freedom of the second subsystem and an expansion coefficient that has two indices,

J and mu for both of the sums here and the product state. So that's like the general

expression for a state written in terms of the basis states of the product basis.

And so this includes states like, which are called entangled because you cannot write them

as a product for states on the subsystems. Important consequences of that are that the

Hilbert space dimension grows like two to the power n, where n is the number of qubits.

If it's, so for the example of a Hilbert space for n qubits, so the important thing is that this

grows exponentially in the number of subsystems. And so then I introduced an object called the

reduced density matrix, which you can write as the trace over one of the subsystems,

say subsystem B. So the reduced density matrix for subsystem A of a projector onto the common

global state of both subsystems. And so from this, I went on to say how you can describe dissipation,

because dissipation in a system, you can understand that each, all of the systems that we look at in

experiments are actually subsystems of a composite system, strictly speaking the entire universe,

but there will be some relevant surrounding which influences that subsystem that we are talking

about. So if we want to describe dissipation, we actually need to describe the dynamics of a

reduced density matrix. And the equation of motion for such a reduced density matrix is called a

master equation. And so dissipation in terms of a master equation, and that says that the time

derivative of a reduced density matrix is equal to commutator of H with this reduced, so that's the

subsystem Hamiltonian. And then I was describing two dissipation terms. And the second one for

purely phasing. Okay, and the effect of these two terms were actually the subject of the exercise

sheet for this afternoon's tutorial. Okay, so with this part of last lecture, that's what completes

the things that I wanted to say about the quantum mechanics background for what is now to come in

discussing really quantum computing. So in today's lecture, I want to start discussing quantum

mechanics. So of course, like what I'd ideally like to teach here is conceptually, okay, how do I

build a good quantum algorithm that provides some speed up over classical ones. But strictly

speaking, we don't have that understanding yet that there is a like general concept. I would

say no general concept yet. There are however common ideas.

So what I do is look at the most important examples. And I hope I get to show you that there is some,

that these have some common features. Yeah. But apart from that, there is a need for useful and

also I call them implementable quantum algorithms. And that need is becoming more and more apparent

these days as the hardware is doing nice progress, right? I guess everyone has seen the media

announcements last week. So there's definitely stuff happening on the hardware side and that

really generates a need for new algorithms. So in some sense, it's a future task for you,

develop some good algorithms for stuff that one can do with early quantum computers.

So here I want to start with a simple example that has the main features to get you one of the main

ideas. So that is Deutsch's problem. So this is an elementary example, say. It won't have